1. Field of the Invention
The present invention relates to a buffer device which is particularly suitable for ATM(asynchronous transfer mode) communication system.
2. Description of the Background Art
Recently, much attentions have been paid to ATM in which information transfer capacities of a communication network are utilized in accordance with requests from communication terminals, as oppose to STM(synchronous transfer mode) in which the information transfer capacities necessary for communications are reserved in advance.
In ATM, information is transferred in terms of short packets of fixed lengths called cells, and the information transfer capacities of the communication network are utilized by each communication terminal by sending the cells to the communication network whenever a need arises.
Compared with STM, ATM possesses advantages of being capable to provide an appropriate information transfer speed required by an individual communication terminal, and also to improve a communication efficiency because of the fact that the information transfer capacities of the communication network are utilized in accordance with requests from the communication terminals.
For this reason, ATM is considered to be a fundamental technique in constructing B-ISDN(broadband-integrated services digital network) system in which information in diverse forms such as audio signals, visual signals, and computer data can be handled in a single unified manner.
As mentioned above, in a communication system utilizing ATM, the information transfer capacities of a communication network are utilized in accordance with requests from the communication terminals. From a point of view of the communication network, this means the communication terminals are sharing communication paths in a demand-driven manner.
Now, for any system, not necessarily limited to the communication system with ATM, in which some kind of resources are shared in a demand-driven manner by terminals, buffer devices are indispensable.
Such a buffer device must be equipped with an ability to temporarily store a number of request data representing requests from different terminals, such as cells in the communication system with ATM, so as to be able to handle plurality of requests to utilize a single resource in order.
This temporary storage ability is usually realized by employing a so called FIFO (First In First Out) buffer in which request data arrived first goes out first, such that the earliest request to utilize the resource will be given a priority over the subsequent requests.
Here, however, when there are certain requests which should be given a higher priority than other requests, such FIFO buffer is obviously inadequate.
In such a case, it is necessary to have priority order established, accompany each request data with priority information indicating priority level of the request, and control the buffer output such that the request data with the highest priority goes out first.
Conventionally, this is achieved by providing separate FIFO buffers for each priority levels, such that the request data with the highest priority which arrived first among all the request data with the highest priority goes out first.
In such a conventional buffer structure, when one FIFO buffer for a particular priority level becomes full, subsequent request data with that priority level will be disregarded. Thus, when the request data for a particular priority data, a memory capacities of the entire buffer structure will be utilized at low efficiency, because a large number of the request data with that particular priority level will be disregarded while the memory capacities for the other priority levels are still available.
To cope with such a problem, there has been a proposition of a multi-queue buffers by Y. Tamir and G. L. Frazier in "High-Performance Multi-Queue Buffers for VLSI Communication Switch", Proceeding of International Conference on Computer Architecture '88, May 30-June 2, 1988.
However, in their multi-queue buffers, link-lists were utilized in realizing the multi-queue, so that it has been difficult to adapt their multi-queue buffers to a high speed buffer implementation.